#include "AffectBipTest.h"
#include <algorithm>
using namespace std;

struct TraverseHelper{
	GNode* current_gnode;
	vector<GNode*> active_path;
	stack<GNode*> current_call_stack;
	stack<vector<int>> visited_stack;
	bool active;
};

bool EqualPath(vector<GNode*>& left, vector<GNode*>& right){
	if(left.size() != right.size()) return false;
	for(int i = 0; i < left.size(); i++){
		if(left[i]->stmt_num != right[i]->stmt_num) return false;
	} 
	return true;
}

bool ComparePath(vector<GNode*>& left, vector<GNode*>& right){
	if(left.size() < right.size()) return true;
	if(left.size() > right.size()) return false;
	for(int i = 0; i < left.size(); i++){
		if(left[i]->stmt_num < right[i]->stmt_num) return true;
		if(left[i]->stmt_num > right[i]->stmt_num) return false;
	} 
	return true;
}

void UniquePath(vector<vector<GNode*>>& path_set){
	if(path_set.empty()) return;
	for(int i = path_set.size() - 1; i > 0 ; i--){
		for(int j = 0; j < i; j++){
			if(!ComparePath(path_set[j],path_set[j+1])){
				path_set[j].swap(path_set[j+1]);
			}
		}
	}
	vector<GNode*>& temp = path_set[0];
	vector<vector<GNode*>> new_path_set;
	new_path_set.push_back(temp);
	for(int i = 1; i < path_set.size(); i++){
		if(EqualPath(temp,path_set[i])) continue;
		temp = path_set[i];
		new_path_set.push_back(temp);
	}
	path_set.swap(new_path_set);
}

void CopyHelper(TraverseHelper* parent,TraverseHelper* child){
	child->active = parent->active;
	child->active_path = parent->active_path;
	child->current_call_stack = parent->current_call_stack;
	child->current_gnode = NULL;
	child->visited_stack = parent->visited_stack;
}

bool IsAffectBipTest(StmtNum left, StmtNum right){
	if(StmtTable::GetStmtTNode(left)->type != ASSIGN_TYPE || StmtTable::GetStmtTNode(right)->type != ASSIGN_TYPE){
		cout << "not assignment!" << endl;
		return false;
	}
	if(!Uses::IsUsesS(right,StmtTable::GetStmtTNode(left)->child->value)){
		//cout << "left does not modify variables used by right" << endl;
		return false;
	}
	/*if(!NextBip::IsNextBipAdv(left,right)){
		cout << "do not have a path" << endl;
		return false;
	}*/
	
	/* to store every path between statement left and right */
	vector<vector<GNode*>> path_set;

	/* store the traverser information */
	stack<TraverseHelper*> path_stack;

	GNode* start_gnode = ProcTable::GetProcCFGRoot(1);
	TraverseHelper* traverser = new TraverseHelper;
	traverser->active = false;
	traverser->current_gnode = start_gnode;
	vector<int> visited(StmtTable::GetSize(),0);
	traverser->visited_stack.push(visited);

	path_stack.push(traverser);
	VarIdx modified_var = StmtTable::GetStmtTNode(left)->child->value;
	while(!path_stack.empty()){
		GNode* next_gnode = NULL;
		traverser = path_stack.top();
		path_stack.pop();
		/* add the active path */
		/*if(traverser->active 
			&& traverser->current_gnode->g_type == ASSIGN_TYPE
			){
			traverser->active_path.push_back(traverser->current_gnode);
		}*/

		switch(traverser->current_gnode->g_type){
		case ASSIGN_TYPE:
		{
			if(traverser->current_gnode->stmt_num == left && !traverser->active){
				traverser->active = true;
				//traverser->active_path.push_back(traverser->current_gnode);
			}
			else if(traverser->current_gnode->stmt_num != right && traverser->active){
				if(Modifies::IsModifiesS(traverser->current_gnode->stmt_num,modified_var)) continue;
			}
			else if(traverser->current_gnode->stmt_num == right && traverser->active){
				/*traverser->active = false;
				for(int i = 1; i < traverser->active_path.size()-1; i++){
					bool affect = true;
					for(int j = 1; j <traverser->active_path.size()-1; j++){
						if(Modifies::IsModifiesS(traverser->active_path[j]->stmt_num,modified_var)){
							affect = false;
							break;
						}
					}
					if(affect) return true;
				}*/
				//path_set.push_back(traverser->active_path);
				/*if(left == right){
					traverser->active_path.clear();
					traverser->active = true;
					traverser->active_path.push_back(traverser->current_gnode);
				}*/
				return true;
			}
			next_gnode = traverser->current_gnode->next_a;
			break;
		}
		
		case WHILE_TYPE:
		{
			if(traverser->visited_stack.top()[traverser->current_gnode->stmt_num-1] == 0){
				traverser->visited_stack.top()[traverser->current_gnode->stmt_num-1]++;
				TraverseHelper* child_1 = new TraverseHelper;
				CopyHelper(traverser,child_1);
				child_1->current_gnode = traverser->current_gnode->next_a;
				path_stack.push(child_1);

				next_gnode = traverser->current_gnode->next_b;
				break;
			}
			else if(traverser->visited_stack.top()[traverser->current_gnode->stmt_num-1] == 1){
				traverser->visited_stack.top()[traverser->current_gnode->stmt_num-1]++;
				TraverseHelper* child_1 = new TraverseHelper;
				CopyHelper(traverser,child_1);
				child_1->current_gnode = traverser->current_gnode->next_a;
				path_stack.push(child_1);

				next_gnode = traverser->current_gnode->next_b;
				break;
			}
			else{
				traverser->visited_stack.top()[traverser->current_gnode->stmt_num-1] = 0;
				delete traverser;
				continue;
			}
		}
		
		case IF_TYPE:
		{
			TraverseHelper* child_1 = new TraverseHelper;
			TraverseHelper* child_2 = new TraverseHelper;
			CopyHelper(traverser,child_1);
			CopyHelper(traverser,child_2);
			child_1->current_gnode = traverser->current_gnode->next_a;
			child_2->current_gnode = traverser->current_gnode->next_b;
			path_stack.push(child_2);
			path_stack.push(child_1);
			delete traverser;
			continue;
		}
			
		case CALL_TYPE:
		{
			TraverseHelper* child_1 = new TraverseHelper;
			CopyHelper(traverser,child_1);
			child_1->current_gnode = ProcTable::GetProcCFGRoot(StmtTable::GetStmtTNode(
				traverser->current_gnode->stmt_num)->value);
			child_1->current_call_stack.push(traverser->current_gnode);
			child_1->visited_stack.push(visited);
			path_stack.push(child_1);
			continue;
		}


		}

		bool path_finished = false;
		while(next_gnode == NULL){
			if(traverser->current_call_stack.empty()){
				path_finished = true;
				break;
			}
			next_gnode = traverser->current_call_stack.top()->next_a;
			traverser->current_call_stack.pop();
			traverser->visited_stack.pop();
		}
		if(path_finished) continue;

		TraverseHelper* child = new TraverseHelper;
		CopyHelper(traverser,child);
		child->current_gnode = next_gnode;
		path_stack.push(child);

		delete traverser;
	}
	return false;
	/*UniquePath(path_set);*/

	/*for(int i = 0; i < path_set.size(); i++){
		cout << "path " << i << ": ";
		for(vector<GNode*>::iterator it = path_set[i].begin(); it != path_set[i].end(); it++){
			cout << (*it)->stmt_num << " ";
		}
		cout << endl;
	}*/

	
	/*for(int i = 0; i < path_set.size(); i++){
		bool affect = true;
		for(int j = 1; j < path_set[i].size()-1; j++){
			if(Modifies::IsModifiesS(path_set[i][j]->stmt_num,modified_var)){
				affect = false;
				break;
			}
		}
		if(affect) return true;
	}
	return false;*/
}